bool fun(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
class Solution {
public:
    int maxVowels(string s, int k) {
        int ret = 0, tmp = 0;
        for(int i = 0;i<s.size();i++){
            if(fun(s[i])) tmp++;
            // if(i < k ) continue;
            if(i >= k && fun(s[i - k])) tmp--;
            ret = max(ret,tmp); 
        }
        return ret;
    }
};
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        
        vector<int> vv(nums.size());
        for(int i = 0; i < nums.size();i++){
            if(i != 0)  vv[i] +=vv[i - 1];
            if(i >= k ) vv[i] -= nums[i - k];
            vv[i]+= nums[i];
        }
        double ret = -100000000;
        for(int i = k-1;i<nums.size();++i){
            ret = max(ret,(double)vv[i]);
        }
        return ret/k;
    }
};
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        threshold *= k;
        int ret = 0;
        vector<int> dp(arr.size());
        for(int i = 0; i < arr.size();i++)
        {
            if(i != 0) {
                dp[i] += dp[i - 1];
            }
            dp[i] += arr[i];
            if(i >= k){
                dp[i] -= arr[i - k];
            }
            if(i >= k - 1){
                if(dp[i] >= threshold) ret++;
            }
        }
        // for(auto i : dp){
        //     cout <<i <<' ';
        // }
        return ret;
    }
};
using ll = long long;
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        vector<ll> dp(nums.size());
        int len = 2 * k + 1;
        for (int i = 0; i < nums.size(); i++) {
            dp[i] += nums[i];
            if (i != 0)
                dp[i] += dp[i - 1];
            if (i >= len)
                dp[i] -= nums[i - len];
        }
        // for (auto e : dp) {
        //     cout << e << ' ';
        // }
        vector<int> ret(nums.size(), -1);
        for (int i = len - 1; i < dp.size(); i++) {
            ret[i - k] = dp[i] / len;
        }
        return ret;
    }
};
class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int max_block = 0;
        int block = 0;
        for(int i = 0;i < blocks.size();i++)
        {
            if(blocks[i] == 'B'){
                block++;
            }
            if(i >= k && blocks[i - k] == 'B')
                block--;
            max_block = max(max_block,block);
        }
        return k - max_block;
    }
};

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
         if(k < 0){
            for(int i = 0; 2*i <code.size();i++) swap(code[i],code[code.size() - i - 1]);
            auto ret = decrypt(code,-k);
            for(int i = 0; 2*i <code.size();i++) swap(ret[i],ret[code.size() - i - 1]);
            return ret;
        }  
        vector<int> dp(code.size());
        int size = code.size();
        if(k == 0) return dp;    

        for(int i = 0;i <k;i++) dp[0] += code[(i + 1) % size];
        for(int i = 1;i <code.size();i++){
            // dp[1] = dp[0] - dp[1] + code[0]
            dp[i] = dp[i - 1] - code[i] + code[(i + k)%size];
        }
        return dp;
    }
};
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int ret = 0;
        vector<int> ans(customers.size());
        ans[0] = customers[0];
        for (int i = 1; i < customers.size(); i++) {
            ans[i] = ans[i - 1] + customers[i];
            if (i >= minutes)
                ans[i] -= customers[i - minutes];
        }
        vector<int> left(customers.size()), right(customers.size());
        for (int i = 0; i < customers.size(); i++) {
            if (grumpy[i] == 0) {
                if (i != 0)
                    left[i] += left[i - 1];
                left[i] += customers[i];
            } else
                left[i] = 0;
        }
        for (int i = customers.size() - 1; i >= 0; i--) {
            if (grumpy[i] == 0) {
                if (i + 1 != customers.size())
                    right[i] += right[i + 1];
                right[i] += customers[i];
            } else
                right[i] = 0;
        }
        for (int i = minutes; i < customers.size(); i++) {
            int t1 = i == minutes ? 0 : left[i - minutes - 1];
            int t2 = (i == customers.size() - 1? 0 : right[i+1]);
            ret = max(ret, t1 + t2 + ans[i]);
        }
        for (auto e : ans)
            cout << e << ' ';
        cout << endl;
        for (auto e : left)
            cout << e << ' ';
        cout << endl;
        for (auto e : right)
            cout << e << ' ';
        cout << endl;
        return 0;
    }
};
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int size = customers.size();
        vector<int> ans(size); // 统计 i下标前minutes个位置grumpy[i] = 1 的总和
        int ret = 0;
        for(int i = 0; i< size;i++){
            if(i != 0) ans[i] += ans[i - 1];
            if(grumpy[i] == 1)  ans[i] += customers[i];
            if(i >= minutes && grumpy[i - minutes] == 1) ans[i] -= customers[i - minutes];
            if(grumpy[i] == 0) ret += customers[i]; 
        }
        int m = 0;
        for(auto e : ans){
            m = max(m,e);
        //    cout<<e<<' ';
        }
        return ret + m;
    }
};
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        long long num = 0;
        for (int i = 0; i < k - 1; i++) {
            if(i > s.size()) return false;
            num = (num << 1) + (s[i] == '1' ? 1 : 0);
        }
        set<long long> ss;
        for (int i = k - 1; i < s.size(); i++) {
            num = ((num << 1) + (s[i] == '1' ? 1 : 0)) % (1 << k);
           // cout << num<<' ';
            ss.insert(num);
        }
        cout << ss.size() <<endl;
        return (long long)ss.size() == (1 << k);
    }
};
class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        map<int, int> mm;
        long long node = 0, sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (mm[nums[i]])
                node++;
            mm[nums[i]]++;
            sum += nums[i];
            if (i >= k) {
                mm[nums[i - k]]--;
                if (mm[nums[i - k]])
                    node--;

                sum -= nums[i - k];
                // cout << sum << ' ';
            }
            if (i >= k - 1 && node + m <= k) {
                ret = max(ret, sum);
            }
            cout << node << ' ';
        }
        return ret;
    }
};
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        map<int, int> ss;
        long long ret = 0, sum = 0;
        for(int i = 0;i <nums.size();i++){
            sum += nums[i], ss[nums[i]]++;
            if (i >= k) {
                sum -= nums[i - k],ss[nums[i - k]]--;
                if (ss[nums[i - k]] == 0)
                    ss.erase(nums[i - k]);
            }
            if (ss.size() == k) {
                ret = max(ret, sum);
            }
        }
        return ret;
    }
};
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int ret = 0, sum = 0;
        for(int i = 0;i < k;i++) sum+=cardPoints[i];
        ret = sum;
        int leftpos = k; // 左边拿了k张牌
        int size = cardPoints.size();
        while(leftpos > 0){
            sum -= cardPoints[leftpos - 1];
            sum += cardPoints[(size - 1) - (k - leftpos)];
            ret = max(ret,sum);
            leftpos--;
        }
        return ret;
    }
}
class Solution {
public:
    int maxFreq(string s, int k, int minSize, int maxSize) {
        unordered_map<string, int> mm;
        unordered_map<char, int> cmm;
        for (int i = 0; i < s.size(); i++) {
            cmm[s[i]]++;
            if (i >= minSize) {
                cmm[s[i - minSize]]--;
                if (cmm[s[i - minSize]] == 0) cmm.erase(s[i - minSize]);
            }
            if (i + 1 >= minSize && cmm.size() <= k) {
                mm[s.substr(i - minSize + 1, minSize)]++;
            }
        }
        int ret = 0;
        for (auto& e : mm) {
            ret = max(ret, e.second);
            cout << e.first << ' ' << e.second;
        }
        return ret;
    }
};class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        int datas[110];
        vector<int> ret(nums.size() - k + 1);
        for(int i = 0;i < nums.size();i++){
            datas[nums[i] + 50]++;
            if(i >= k) 
            datas[nums[i - k] + 50]--;
            if(i + 1>= k){
                int j = 0;
                for(int tmp = 0;tmp < x;j++){
                    tmp += datas[j];
                }
                ret[i - k + 1] = min(j-51,0);
            }
        }
        return ret;
    }
};